package controller;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;

import model.PlayingField;

public class ArtificialSolver {
	
	
public void printGameState(PlayingField pf){
		
		boolean[][] gameState = pf.getGameState();
		
		int height = gameState.length;
		int width = gameState[0].length;
		
		for(int y=height-1;y>=0;y--){
			for(int x=0;x<width;x++){
				if(x==0){
					System.out.println("");
				}
				if(pf.getGameState()[x][y]==true){
					System.out.print("x ");
				}
				else{
					System.out.print("o ");
				}
			}
		}
		System.out.println("");
	}

	public boolean isMoveForwardValid(PlayingField pf, int xStart, int yStart, int xEnd, int yEnd){
		boolean[][] gameState = pf.getGameState();
		int height = gameState.length;
		int width = gameState[0].length;
		
		if(xStart <0 || yStart<0 || xEnd<0 || yEnd<0){
//			System.out.println("Error: isMoveValid: start or endposition not in gamefield!");
			return false;
		}
		else if(xStart+1>width || xEnd+1>width){
//			System.out.println("Error: isMoveValid: start or endposition not in gamefield1!");
			return false;
		}
		else if(yStart+1>height || yEnd+1>height){
//			System.out.println("Error: isMoveValid: start or endposition not in gamefield2!");
			return false;
		}
				
		if(pf.getField()[xStart][yStart]==false || pf.getField()[xEnd][yEnd]==false){
//			System.out.println("Error: isMoveValid: start or endposition not in gamefield3!");
			return false;
		}
		//until here: assertion that x,yStart and x,yEnd are in the game field.
		
		if(gameState[xEnd][yEnd] == true){
//			System.out.println("Error: isMoveValid: ball in Endposition!");
			return false;
		}
		if(gameState[xStart][yStart] == false){
//			System.out.println("Error: isMoveValid: No ball in Startposition!");
			return false;
		}
		//until here: assert landing position is free and start position is not
		
		if(xStart-xEnd != 0 && yStart-yEnd != 0){
//			System.out.println("Error: isMoveValid: start and endposition not in same row+column!");
			return false;
		}
		else if(xStart-xEnd == 0 && (yStart-yEnd)*(yStart-yEnd) != 4){
//			System.out.println("Error: isMoveValid: start and endposition not in same row+column1!");
			return false;
		}
		else if((xStart-xEnd)*(xStart-xEnd) != 4 && yStart-yEnd == 0){
//			System.out.println("Error: isMoveValid: start and endposition not in same row+column2!");
			return false;
		}
		//until here: assert start- and endpositions are exactly 2 spaces away
		
		if(xStart-xEnd == -2 && gameState[xStart+1][yStart] == false){
//			System.out.println("Error: isMoveValid: no ball between 2 positions!");
			return false;
		}
		else if(xStart-xEnd == 2 && gameState[xStart-1][yStart] == false){
//			System.out.println("Error: isMoveValid: no ball between 2 positions1!");
			return false;
		}
		else if(yStart-yEnd == -2 && gameState[xStart][yStart+1] == false){
//			System.out.println("Error: isMoveValid: no ball between 2 positions2!");
			return false;
		}
		else if(yStart-yEnd == 2 && gameState[xStart][yStart-1] == false){
//			System.out.println("Error: isMoveValid: no ball between 2 positions3!");
			return false;
		}
		//until here: assert there is a ball between the two positions
		
		return true;
	}
	
	
	
	
	public boolean isMoveBackwardValid(PlayingField pf, int xStart, int yStart, int xEnd, int yEnd){
		boolean[][] gameState = pf.getGameState();
		int height = gameState.length;
		int width = gameState[0].length;
		
		if(xStart <0 || yStart<0 || xEnd<0 || yEnd<0){
			return false;
		}
		else if(xStart+1>width || xEnd+1>width){
			return false;
		}
		else if(yStart+1>height || yEnd+1>height){
			return false;
		}
				
		if(pf.getField()[xStart][yStart]==false || pf.getField()[xEnd][yEnd]==false){
			return false;
		}
		//until here: assertion that x,yStart and x,yEnd are in the game field.
		
		if(gameState[xEnd][yEnd] == true){
			return false;
		}
		if(gameState[xStart][yStart] == false){
			return false;
		}
		//until here: assert landing position is free and start position is not
		
		if(xStart-xEnd != 0 && yStart-yEnd != 0){
			return false;
		}
		else if(xStart-xEnd == 0 && (yStart-yEnd)*(yStart-yEnd) != 4){
			return false;
		}
		else if((xStart-xEnd)*(xStart-xEnd) != 4 && yStart-yEnd == 0){
			return false;
		}
		//until here: assert start- and endpositions are exactly 2 spaces away
		
		if(xStart-xEnd == -2 && gameState[xStart+1][yStart] == true){
			return false;
		}
		else if(xStart-xEnd == 2 && gameState[xStart-1][yStart] == true){
			return false;
		}
		else if(yStart-yEnd == -2 && gameState[xStart][yStart+1] == true){
			return false;
		}
		else if(yStart-yEnd == 2 && gameState[xStart][yStart-1] == true){
			return false;
		}
		//until here: assert there is no ball between the two positions
		
		return true;
	}
	
	public PlayingField moveForward(PlayingField pfOld, int xStart, int yStart, int xEnd, int yEnd){
		PlayingField pf = new PlayingField();
		pf.setGameState(pfOld.getGameState());
		
		LinkedList<MoveForward> oldListWithMovesForward = pfOld.getListWithMovesForward();
		LinkedList<MoveForward> newListWithMovesForward = new LinkedList<MoveForward>();
		for(int i=0;i<oldListWithMovesForward.size();i++){
			newListWithMovesForward.add(oldListWithMovesForward.get(i));
		}
		
		Stack<MoveForward> oldMovesForward = pfOld.getStackForward();
		Stack<MoveBackward> oldMovesBackward = pfOld.getStackBackward();
		MoveBackward mb=null;
		if(!oldMovesBackward.isEmpty()){
			mb = oldMovesBackward.pop();
			oldMovesBackward.push(mb);
		}
		
		
		if(isMoveForwardValid(pf, xStart, yStart, xEnd, yEnd)){
			
			newListWithMovesForward.add(new MoveForward(xStart, yStart, xEnd, yEnd));
			
			if((new MoveForward(xStart, yStart, xEnd, yEnd)).isOpposite(mb)){
				oldMovesForward.push(new MoveForward(xStart, yStart, xEnd, yEnd));
				oldMovesBackward.pop();
			}
			else{
				oldMovesForward.push(new MoveForward(xStart, yStart, xEnd, yEnd));
				oldMovesBackward.clear();
			}
			
			
			pf.setStone(xStart, yStart, false);
			pf.setStone(xEnd, yEnd, true);
			if(xStart-xEnd == -2){
				pf.setStone(xStart+1, yStart, false);
			}
			else if(xStart-xEnd == 2){
				pf.setStone(xStart-1, yStart, false);
			}
			else if(yStart-yEnd == -2){
				pf.setStone(xStart, yStart+1, false);
			}
			else if(yStart-yEnd == 2){
				pf.setStone(xStart, yStart-1, false);
			}
		}
		
		pf.setStackBackward(oldMovesBackward);
		pf.setStackForward(oldMovesForward);
		pf.setListWithMovesForward(newListWithMovesForward);

		return pf;
	}
	/**
	 * startpoint for move backwards is always true, other two points need to be false
	 * @param pf
	 * @param xStart
	 * @param yStart
	 * @param xEnd
	 * @param yEnd
	 * @return 
	 */
	public PlayingField moveBackward(PlayingField pfOld, int xStart, int yStart, int xEnd, int yEnd){
		PlayingField pf = new PlayingField();
		pf.setGameState(pfOld.getGameState());
		
		LinkedList<MoveForward> oldListWithMovesForward = pfOld.getListWithMovesForward();
		LinkedList<MoveForward> newListWithMovesForward = new LinkedList<MoveForward>();
		for(int i=0;i<oldListWithMovesForward.size();i++){
			newListWithMovesForward.add(oldListWithMovesForward.get(i));
		}
		
		Stack<MoveForward> oldMovesForward = pfOld.getStackForward();
		Stack<MoveBackward> oldMovesBackward = pfOld.getStackBackward();
		MoveForward mf=null;
		if(!oldMovesForward.isEmpty()){
			mf = oldMovesForward.pop();
			oldMovesForward.push(mf);
		}
		
		
		
		if(this.isMoveBackwardValid(pf, xStart, yStart, xEnd, yEnd)){
			
			oldListWithMovesForward.removeLast();
			
			if((new MoveBackward(xStart, yStart, xEnd, yEnd)).isOpposite(mf)){
				oldMovesBackward.push(new MoveBackward(xStart, yStart, xEnd, yEnd));
				oldMovesForward.pop();
				
			}
			else{
				oldMovesBackward.push(new MoveBackward(xStart, yStart, xEnd, yEnd));
				oldMovesForward.clear();
			}
			
			
			pf.setStone(xStart, yStart, false);
			pf.setStone(xEnd, yEnd, true);
			if(xStart-xEnd == -2){
				pf.setStone(xStart+1, yStart, true);
			}
			else if(xStart-xEnd == 2){
				pf.setStone(xStart-1, yStart, true);
			}
			else if(yStart-yEnd == -2){
				pf.setStone(xStart, yStart+1, true);
			}
			else if(yStart-yEnd == 2){
				pf.setStone(xStart, yStart-1, true);
			}
		}
		
		pf.setStackBackward(oldMovesBackward);
		pf.setStackForward(oldMovesForward);
		pf.setListWithMovesForward(newListWithMovesForward);
		
		return pf;
	}
	
	/**
	 * probably gonna have some problems with pf.getField().length if field not quadratic
	 * @param pf
	 * @return 
	 */
	public LinkedList<MoveForward> findAllPossibleMovesForward(PlayingField pf){
		LinkedList<MoveForward> possibleMoves = new LinkedList<MoveForward>();
		for(int i=0; i<pf.getField().length; i++){
			for(int j=0; j<pf.getField()[0].length-2; j++){
				if(this.isMoveForwardValid(pf, j, i, j+2, i)){
					possibleMoves.add(new MoveForward(j, i, j+2, i));
				}
			}
		}
		
		for(int i=0; i<pf.getField().length-2; i++){
			for(int j=0; j<pf.getField()[0].length; j++){
				if(this.isMoveForwardValid(pf, j, i, j, i+2)){
					possibleMoves.add(new MoveForward(j, i, j, i+2));
				}
			}
		}
		
		for(int i=0; i<pf.getField().length; i++){
			for(int j=2; j<pf.getField()[0].length; j++){
				if(this.isMoveForwardValid(pf, j, i, j-2, i)){
					possibleMoves.add(new MoveForward(j, i, j-2, i));
				}
			}
		}
		
		for(int i=0; i<pf.getField().length; i++){
			for(int j=2; j<pf.getField()[0].length; j++){
				if(this.isMoveForwardValid(pf, j, i, j, i-2)){
					possibleMoves.add(new MoveForward(j, i, j, i-2));
				}
			}
		}
		
		return possibleMoves;
	}
	
	
	
	public IterationStep iterateOneStepForward(int iterationStep, LinkedList<PlayingField> pf,
			LinkedList<LinkedList<LinkedList<MoveForward>>> steps){
		
		LinkedList<PlayingField> newPfs = new LinkedList<PlayingField>();
		 HashMap<PlayingField, Double> hm = new HashMap<PlayingField, Double>();
//		LinkedList<LinkedList<LinkedList<MoveForward>>> newSteps = 
//				new LinkedList<LinkedList<LinkedList<MoveForward>>>();
		
		int debugCount=0;
		
		
		while(pf.size()>0){
			LinkedList<MoveForward> moves = this.findAllPossibleMovesForward(pf.get(0));
			PlayingField tempPf = pf.get(0);
			pf.remove(0);
			
//			boolean stepsEmpty=false;
//			if(steps.size()==0){
//				stepsEmpty=true;
//			}
//			LinkedList<LinkedList<MoveForward>> TotalSteps = new LinkedList<LinkedList<MoveForward>>();
//			if(!stepsEmpty){
//				TotalSteps = steps.get(0);
//				steps.remove(0);
//			}
			
			while(moves.size()>0){
				
				 PlayingField pfToAdd = this.moveForward(tempPf, moves.get(0).getxStart(),
						moves.get(0).getyStart(), moves.get(0).getxEnd(), moves.get(0).getyEnd());
				
				int alreadyExists=-1;
//				for(int i=0; i<newPfs.size(); i++){
					
					if(hm.containsKey(pfToAdd)){
						alreadyExists=0;
					}
					
//					if(newPfs.get(i).equals1(pfToAdd)){
//						alreadyExists=i;
//						break;
//					}
//				}
				
				if(alreadyExists>=0){
//					System.out.println("dadada");
					
//					if(!stepsEmpty){
//						LinkedList<MoveForward> temp2 = new LinkedList<MoveForward>();
//						for(int i=0; i<TotalSteps.size(); i++){
//							temp2 = TotalSteps.get(i);
//							temp2.add(moves.get(0));
//						}
//						newSteps.get(alreadyExists).add(temp2);
//					}
					
					
					
				}
				else{
					
					hm.put(pfToAdd, 1.0);
//					newPfs.add(pfToAdd);
//					debugCount++;
//					System.out.println(debugCount);
					
//					System.out.println("dududu");
//					LinkedList<LinkedList<MoveForward>> temp1 = new LinkedList<LinkedList<MoveForward>>();
//					
//					if(!stepsEmpty){
//						for(int i=0; i<TotalSteps.size(); i++){
//							LinkedList<MoveForward> temp2 = TotalSteps.get(i);
//							temp2.add(moves.get(0));
//							temp1.add(temp2);
//						}
//					}
//					
//					
//					newSteps.add(temp1);
				}
				
				moves.remove(0);
			}
			
		}
		Iterator<PlayingField> it = hm.keySet().iterator();
		while(it.hasNext()){
			newPfs.add(it.next());
			it.remove();
			
		}
		
		IterationStep result = new IterationStep(newPfs, null);// newSteps
		return result;
		
	}
	
	/**
	 * WARNING! Only will work work for the cross!
	 * @param st
	 */
	public void doDFS(Stack<DFSObject> st, LinkedList<DFSObject> solutions){
		if(st.empty()){
			System.out.println("Finished with DFS!");
		}
		else{
			DFSObject currentObj = st.pop();
			if(currentObj.getIteration()==1 && currentObj.getPlayingField().getGameState()[4][4]==true){
				System.out.println("Solution found!!! Size:"+currentObj.getSteps().size());
				solutions.add(currentObj);
				for(int i=0;i<currentObj.getSteps().size();i++){
					currentObj.getSteps().get(i).printMove();
				}
			}
			LinkedList<MoveForward> possibleMoves= this.findAllPossibleMovesForward(currentObj.getPlayingField());
//			this.printGameState(currentObj.getPlayingField());
//			this.printAllPossibleMovesForward(currentObj.getPlayingField());
			while(!possibleMoves.isEmpty()){
				PlayingField newPf= new PlayingField();
//				newPf.setGameState(currentObj.getPlayingField().getGameState());			
				newPf = this.moveForward(currentObj.getPlayingField(), possibleMoves.get(0).getxStart(), possibleMoves.get(0).getyStart()
						, possibleMoves.get(0).getxEnd(), possibleMoves.get(0).getyEnd());
				
				
				LinkedList<MoveForward> newSteps = new LinkedList<MoveForward>();				
				for(int i=0;i<currentObj.getSteps().size();i++){
					newSteps.add(currentObj.getSteps().get(i));
				}
				newSteps.add(possibleMoves.get(0));
//				System.out.println("newSteps: "+ newSteps.size());
				DFSObject dfsObjToAdd = new DFSObject(newPf,currentObj.getIteration()-1, newSteps);
				st.push(dfsObjToAdd);
				possibleMoves.remove(0);
				doDFS(st, solutions);
			}
//			System.out.println("Iteration: "+ currentObj.getIteration());
//			this.printGameState(currentObj.getPlayingField());
			
		}
	}
	
	/**
	 * this will only work Pe= endposition in the middle
	 * @param pf
	 * @return
	 */
	public int[] buildPse(PlayingField pf){
		
		int numberOfColums = 0;
		int numberOfRows = 0;
		
		int[][] numbersLookUp = new int[pf.getField().length][pf.getField()[0].length];
		
		for(int y=0;y<pf.getField()[0].length;y++){//determine how many moves are possible
			for(int x=0;x<pf.getField().length;x++){
				if(pf.getField()[x][y]==true){
					numbersLookUp[x][y]=numberOfColums;
					numberOfColums++;
				}
			}
		}
		int [] result = new int[numberOfColums];
		for(int i=0;i<numberOfColums;i++){
			result[i]=0;
		}
		for(int y=0;y<pf.getField()[0].length;y++){//determine how many moves are possible
			for(int x=0;x<pf.getField().length;x++){
				if(pf.getField()[x][y]==true){
					int a = numbersLookUp[x][y];
					if(pf.getGameState()[x][y]==true){
						result[a] = 1;
					}
					else{
						result[a] = 0;
					}
					if(x==4 && y==4){
						result[a] -= 1;
					}
				}
			}
		}
		
		return result;
	}
	
	
	public int[][] buildAIJ(PlayingField pf){
		
		int numberOfColums = 0;
		int numberOfRows = 0;
		
		int[][] numbersLookUp = new int[pf.getField().length][pf.getField()[0].length];
		
		for(int y=0;y<pf.getField()[0].length;y++){//determine how many moves are possible
			for(int x=0;x<pf.getField().length;x++){
				if(pf.getField()[x][y]==true){
					numbersLookUp[x][y]=numberOfColums;
					numberOfColums++;
				}
				if(pf.getField()[x][y]==true && x<pf.getField().length-2){
					if(pf.getField()[x+1][y]==true && pf.getField()[x+2][y]==true){
						numberOfRows++;
					}
				}
				if(pf.getField()[x][y]==true && x>1){
					if(pf.getField()[x-1][y]==true && pf.getField()[x-2][y]==true){
						numberOfRows++;
					}
				}
				if(pf.getField()[x][y]==true && y<pf.getField()[0].length-2){
					if(pf.getField()[x][y+1]==true && pf.getField()[x][y+2]==true){
						numberOfRows++;
					}
				}
				if(pf.getField()[x][y]==true && y>1){
					if(pf.getField()[x][y-1]==true && pf.getField()[x][y-2]==true){
						numberOfRows++;
					}
				}
			}
		}
		int[][] result = new int[numberOfRows][numberOfColums];
		
		for(int y = 0;y<numberOfColums;y++){
			for(int x = 0;x<numberOfRows;x++){
				result[x][y]=0;
			}
		}
		
//		System.out.println("Variables: "+ numberOfRows+" Rows: "+ numberOfColums);
		
		int finalRow = 0;
		
		for(int y=0;y<pf.getField()[0].length;y++){//determine how many moves are possible
			for(int x=0;x<pf.getField().length;x++){
				if(pf.getField()[x][y]==true && x<pf.getField().length-2){
					if(pf.getField()[x+1][y]==true && pf.getField()[x+2][y]==true){
						int a = numbersLookUp[x][y];
						int b = numbersLookUp[x+1][y];
						int c = numbersLookUp[x+2][y];
						result[finalRow][a] = 1;
						result[finalRow][b] = 1;
						result[finalRow][c] = -1;
						finalRow++;	
					}
				}
				if(pf.getField()[x][y]==true && x>1){
					if(pf.getField()[x-1][y]==true && pf.getField()[x-2][y]==true){
						int a = numbersLookUp[x][y];
						int b = numbersLookUp[x-1][y];
						int c = numbersLookUp[x-2][y];
						result[finalRow][a] = 1;
						result[finalRow][b] = 1;
						result[finalRow][c] = -1;
						finalRow++;	
					}
				}
				if(pf.getField()[x][y]==true && y<pf.getField()[0].length-2){
					if(pf.getField()[x][y+1]==true && pf.getField()[x][y+2]==true){
						int a = numbersLookUp[x][y];
						int b = numbersLookUp[x][y+1];
						int c = numbersLookUp[x][y+2];
						result[finalRow][a] = 1;
						result[finalRow][b] = 1;
						result[finalRow][c] = -1;
						finalRow++;	
					}
				}
				if(pf.getField()[x][y]==true && y>1){
					if(pf.getField()[x][y-1]==true && pf.getField()[x][y-2]==true){
						int a = numbersLookUp[x][y];
						int b = numbersLookUp[x][y-1];
						int c = numbersLookUp[x][y-2];
						result[finalRow][a] = 1;
						result[finalRow][b] = 1;
						result[finalRow][c] = -1;
						finalRow++;	
					}
				}
			}
		}
		
		return result;
	}
	

    // Gaussian elimination with partial pivoting
    public int[] lsolve(int[][] A, int[] b) {
        int N  = b.length;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {        
                for (int k = i; k < N; k++) {
                    
                }
            }
        }
        
        return null;
    }
	
	
	public void printAllPossibleMovesForward(PlayingField pf){
		LinkedList<MoveForward> moves = this.findAllPossibleMovesForward(pf);
		while(moves.size()>0){
			System.out.print("["+moves.get(0).getxStart()+",");
			System.out.print(moves.get(0).getyStart()+"],[");
			System.out.print(moves.get(0).getxEnd()+",");
			System.out.print(moves.get(0).getyEnd()+"] ");
			System.out.println("");
			moves.remove(0);
		}
	}
	
	public void saveSolutionsToFile(String filename, LinkedList<DFSObject> solutions){
		PrintWriter writer;
		try {
			writer = new PrintWriter(filename, "UTF-8");
			while(solutions.size()>0){
				for(int i=0;i<solutions.getFirst().getSteps().size();i++){
					writer.print(solutions.getFirst().getSteps().get(i).toString());
				}
				writer.println("");
				solutions.removeFirst();
			}
			writer.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (UnsupportedEncodingException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public LinkedList<DFSObject> loadSolutions(String fileName, PlayingField pf) throws IOException {
		 File file = new File(fileName);
		 StringBuffer content = new StringBuffer();
		 BufferedReader reader = null;
		 LinkedList<DFSObject> result = new LinkedList<DFSObject>();
		 
		 try {
		  reader = new BufferedReader(new FileReader(file));
		  String s = null;

		  while ((s = reader.readLine()) != null) {
			  String[] cells = s.split("<>");
			  LinkedList<MoveForward> moves = new LinkedList<MoveForward>();
			  for(int i =0; i<cells.length-1;i++){
				  cells[i].trim();
				  if(cells[i].startsWith(" ")){
					  String buffer = new String();
					  for(int i1=1;i1<cells[i1].length();i1++){
						  buffer+=cells[i].substring(i1,i1+1);
					  }
					  cells[i]=buffer;
				  }
//				  System.out.println("Start: "+cells[i]);
				  
				 MoveForward mf = new MoveForward(Integer.parseInt(cells[i].substring(1, 2)), 
						 Integer.parseInt(cells[i].substring(3, 4)), Integer.parseInt(cells[i].substring(6, 7))
						 , Integer.parseInt(cells[i].substring(8, 9)));
				 moves.add(mf);
			  }
			  DFSObject solution = new DFSObject(pf, moves.size(), moves);
			  result.add(solution);
			  //				  MoveForward mf = new MoveForward();


			  content.append(s).append(System.getProperty("line.separator"));
		  }
		 } catch (FileNotFoundException e) {
		  throw e;
		 } catch (IOException e) {
		  throw e;
		 } finally {
		  try {
		   if (reader != null) {
		    reader.close();
		   }
		  } catch (IOException e) {
		   throw e;
		  }
		 }
		 return result;
		}
	
	
	public int amountOfSolutionsLeft(LinkedList<DFSObject> solutions, PlayingField pf){
		
		LinkedList<DFSObject> newList = new LinkedList<DFSObject>();
		
		for(int i=0;i<pf.getListWithMovesForward().size();i++){
			newList= new LinkedList<DFSObject>();
			for(int j=0;j<solutions.size();j++){
				if(solutions.get(j).getSteps().get(i).isEqual(pf.getListWithMovesForward().get(i))){
					newList.add(solutions.get(j));
				}
			}
			if(newList.isEmpty()){
				return 0;
			}
			solutions=newList;
			
		}
		
		return solutions.size();
	}
	
}
